{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Campus Bikes II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #dynamic-programming #backtracking #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #动态规划 #回溯 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: assignBikes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #校园自行车分配 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>在由 2D 网格表示的校园里有&nbsp;<code>n</code>&nbsp;位工人（<code>worker</code>）和 <code>m</code>&nbsp;辆自行车（<code>bike</code>），<code>n &lt;= m</code>。所有工人和自行车的位置都用网格上的 2D 坐标表示。</p>\n",
    "\n",
    "<p>我们为每一位工人分配一辆专属自行车，使每个工人与其分配到的自行车之间的 <strong>曼哈顿距离</strong> 最小化。</p>\n",
    "\n",
    "<p>返回 <code>每个工人与分配到的自行车之间的曼哈顿距离的最小可能总和</code> 。</p>\n",
    "\n",
    "<p><code>p1</code> 和&nbsp;<code>p2</code>&nbsp;之间的 <strong>曼哈顿距离</strong> 为&nbsp;<code>Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/03/06/1261_example_1_v2.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>workers = [[0,0],[2,1]], bikes = [[1,2],[3,3]]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>\n",
    "自行车 0 分配给工人 0，自行车 1 分配给工人 1 。分配得到的曼哈顿距离都是 3, 所以输出为 6 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/03/06/1261_example_2_v2.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>workers = [[0,0],[1,1],[2,0]], bikes = [[1,0],[2,2],[2,1]]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>\n",
    "先将自行车 0 分配给工人 0，再将自行车 1 分配给工人 1（或工人 2），自行车 2 给工人 2（或工人 1）。如此分配使得曼哈顿距离的总和为 4。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>workers = [[0,0],[1,0],[2,0],[3,0],[4,0]], bikes = [[0,999],[1,999],[2,999],[3,999],[4,999]]\n",
    "<strong>输出：</strong>4995\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == workers.length</code></li>\n",
    "\t<li><code>m == bikes.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= m &lt;= 10</code></li>\n",
    "\t<li><code>workers[i].length == 2</code></li>\n",
    "\t<li><code>bikes[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= workers[i][0], workers[i][1], bikes[i][0], bikes[i][1] &lt; 1000</code></li>\n",
    "\t<li>所有的工人和自行车的位置都是 <strong>不同</strong>&nbsp;的。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [campus-bikes-ii](https://leetcode.cn/problems/campus-bikes-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [campus-bikes-ii](https://leetcode.cn/problems/campus-bikes-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,0],[2,1]]\\n[[1,2],[3,3]]', '[[0,0],[1,1],[2,0]]\\n[[1,0],[2,2],[2,1]]', '[[0,0],[1,0],[2,0],[3,0],[4,0]]\\n[[0,999],[1,999],[2,999],[3,999],[4,999]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        n=len(workers)\n",
    "        m=len(bikes)\n",
    "        state=(1<<m)\n",
    "        dp=[[float(\"inf\")]*state for _ in range(n+1)]\n",
    "        for j in range(state):\n",
    "            dp[0][j]=0\n",
    "        dis=[[float(\"inf\")]*m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                x,y=workers[i]\n",
    "                x1,y1=bikes[j]\n",
    "                dis[i][j]=abs(x-x1)+abs(y-y1)\n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            for s in range(state):\n",
    "                if bin(s).count(\"1\")!=(i-1):\n",
    "                    continue\n",
    "                for j in range(m):\n",
    "                    if s&(1<<j)==0:\n",
    "                        news=s|(1<<j)\n",
    "                        dp[i][news]=min(dp[i][news],dp[i-1][s]+dis[i-1][j])\n",
    "      #  print(dp)\n",
    "        return min(dp[-1])\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        n, m = len(workers), len(bikes)\n",
    "        dist = [[float('inf')] * m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                dist[i][j] = abs(workers[i][0] - bikes[j][0]) + abs(workers[i][1] - bikes[j][1]) \n",
    "        dp = [[float('inf')] * (1 << m) for _ in range(n+1)]\n",
    "        dp[0][0] = 0 \n",
    "        \n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, 1 << m):\n",
    "                if str(bin(j)).count('1') == i:\n",
    "                    for k in range(m):\n",
    "                        if (j >> k) & 1:\n",
    "                            dp[i][j] = min(dp[i][j], dp[i-1][j^(1<<k)] + dist[i-1][k])\n",
    "        return min(dp[n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        n=len(workers)\n",
    "        m=len(bikes)\n",
    "        state=(1<<m)\n",
    " \n",
    "        dis=[[float(\"inf\")]*m for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                x,y=workers[i]\n",
    "                x1,y1=bikes[j]\n",
    "                dis[i][j]=abs(x-x1)+abs(y-y1)\n",
    "        dp= [[float(\"inf\")]*state for _ in range(n+1)]\n",
    "\n",
    "        for s in range(state):\n",
    "            dp[0][s]=0\n",
    "        for i in range(1,n+1):\n",
    "            for s in range(state):\n",
    "                if bin(s).count(\"1\")==(i-1):\n",
    "                    for j in range(m):\n",
    "                        cur=1<<j\n",
    "                        if s&cur==0:\n",
    "                            news=s|cur\n",
    "                            dp[i][news]=min(dp[i][news],dp[i-1][s]+dis[i-1][j])\n",
    "\n",
    "        print(dp)\n",
    "        return min(dp[-1])\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        def Manhattan(p1, p2):\n",
    "            return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, bike):    # 对第 i 个人，搜索剩余的自行车并尝试分配给他，同时计算距离\n",
    "            if i == m:       # 如果没有人了，返回 0 \n",
    "                return 0\n",
    "            \n",
    "            res = inf\n",
    "            for j in range(n):      # 遍历每个自行车\n",
    "                if bike & (1 << j) == 0:     # 如果未使用过\n",
    "                    # 把 bikes[j] 分配给 workers[i] 并计算距离 ，同时把人的已使用数量加 1、bike 的 mask 赋上值\n",
    "                    res = min(res, Manhattan(workers[i], bikes[j]) + dfs(i+1, bike | (1 << j))) \n",
    "            return res\n",
    "\n",
    "        m = len(workers)\n",
    "        n = len(bikes)\n",
    "        return dfs(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        # 记忆化搜索\n",
    "        n = len(workers)\n",
    "        m = len(bikes)\n",
    "        def Manhattan(a,b):\n",
    "            return abs(a[0]-b[0])+abs(a[1]-b[1])\n",
    "        @cache\n",
    "        def dfs(i,pre):\n",
    "            # 表示给第i个工人选择自行车，已选择的自行车为集合pre，其曼哈顿距离和为dfs(i,pre)\n",
    "            if i == n:\n",
    "                return 0\n",
    "            res = inf\n",
    "            for j in range(m):\n",
    "                if pre & (1 << j) == 0:\n",
    "                    res = min(res,dfs(i+1,pre|(1 << j))+Manhattan(workers[i],bikes[j])) \n",
    "            return res\n",
    "        return dfs(0,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        m, n = len(workers), len(bikes)\n",
    "        def dist(x, y):\n",
    "            return abs(x[0] - y[0]) + abs(x[1] - y[1])\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, bike):\n",
    "            if i == m:\n",
    "                return 0\n",
    "            \n",
    "            ans = inf\n",
    "            for j in range(n):\n",
    "                if bike & (1 << j) == 0:\n",
    "                    ans = min(ans, dfs(i + 1, bike | (1 << j)) + dist(workers[i], bikes[j]))\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def min_(a, b):\n",
    "    return a if a < b else b\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        n = len(workers)\n",
    "        m = len(bikes)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(i, state):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            res = inf\n",
    "            x, y = workers[i]\n",
    "            for j in range(m):\n",
    "                if state & (1<<j):\n",
    "                    a, b = bikes[j]\n",
    "                    cur = abs(x-a)+abs(y-b) + dfs(i+1, state ^ (1<<j))\n",
    "                    res = min_(res, cur)\n",
    "            return res\n",
    "        \n",
    "        return dfs(0, (1<<m)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "      m,n=len(workers),len(bikes)\n",
    "      def getDis(w:List[int],b:List[int])->int:\n",
    "        return abs(w[0]-b[0])+abs(w[1]-b[1])\n",
    "      @cache\n",
    "      def dfs(cur:int,bike_use:int)->int:\n",
    "        if cur==m: return 0\n",
    "        res=float('inf')\n",
    "        for i in range(n):\n",
    "          if bike_use&(1<<i)==0:\n",
    "            res=min(res,getDis(workers[cur],bikes[i])+dfs(cur+1,bike_use|(1<<i)))\n",
    "        return res\n",
    "      return dfs(0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        def Manhattan(p1, p2):\n",
    "            return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, bike): # 对第i个人，搜索剩余的自行车并尝试分配给他，同时计算距离\n",
    "            if i == m:  # 如果没有人了，返回 0 \n",
    "                return 0\n",
    "            \n",
    "            res = inf\n",
    "            for j in range(n):      # 遍历每个自行车\n",
    "                if bike & (1 << j) == 0:   # 如果未使用过 \n",
    "                # 把 bikes[j] 分配给 workers[i] 并计算距离 ，同时把人的已使用数量加 1、bike 的 mask 赋上值\n",
    "                    res = min(res, Manhattan(workers[i], bikes[j]) + dfs(i+1, bike | (1 << j))) \n",
    "            return res\n",
    "\n",
    "        m = len(workers)\n",
    "        n = len(bikes)\n",
    "        return dfs(0, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        def dis(x,y):\n",
    "            return abs(workers[x][0]-bikes[y][0])+abs(workers[x][1]-bikes[y][1])\n",
    "        #状态压缩+记忆化搜索\n",
    "        n,m=len(workers),len(bikes)\n",
    "        #尝试给第i个工人分配自行车\n",
    "        @cache\n",
    "        def dfs(i,mask):\n",
    "            if i==n: return 0\n",
    "            res,cur=0,inf\n",
    "            for j in range(m):\n",
    "                if mask>>j&1:\n",
    "                    cur=min(cur,dfs(i+1,mask^(1<<j))+dis(i,j))\n",
    "            res+=cur\n",
    "            return res\n",
    "        return dfs(0,(1<<m)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        def dis(x,y):\n",
    "            return abs(workers[x][0]-bikes[y][0])+abs(workers[x][1]-bikes[y][1])\n",
    "        #状态压缩+记忆化搜索\n",
    "        n,m=len(workers),len(bikes)\n",
    "        #尝试给第i个工人分配自行车\n",
    "        @cache\n",
    "        def dfs(i,mask):\n",
    "            if i==n: return 0\n",
    "            res,cur=0,inf\n",
    "            for j in range(m):\n",
    "                if mask>>j&1:\n",
    "                    cur=min(cur,dfs(i+1,mask^(1<<j))+dis(i,j))\n",
    "            res+=cur\n",
    "            return res\n",
    "        return dfs(0,(1<<m)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        def dis(x,y):\n",
    "            return abs(workers[x][0]-bikes[y][0])+abs(workers[x][1]-bikes[y][1])\n",
    "        #状态压缩+记忆化搜索\n",
    "        n,m=len(workers),len(bikes)\n",
    "        #尝试给第i个工人分配自行车\n",
    "        #我们利用m位二进制数表达自行车的分配情况,1为可分配,0为已分配。\n",
    "        @cache\n",
    "        def dfs(i,mask):\n",
    "            if i==n: return 0\n",
    "            res,cur=0,inf\n",
    "            for j in range(m):\n",
    "                if mask>>j&1:\n",
    "                    cur=min(cur,dfs(i+1,mask^(1<<j))+dis(i,j))\n",
    "            res+=cur\n",
    "            return res\n",
    "        return dfs(0,(1<<m)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        def Manhattan(a,b):\n",
    "            return abs(a[0]-b[0])+abs(a[1]-b[1])\n",
    "        @cache\n",
    "        def dfs(i,pre):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            res = inf\n",
    "            for j in range(m):\n",
    "                if pre & (1 << j) == 0:\n",
    "                    res = min(res,dfs(i+1,pre|(1 << j))+Manhattan(workers[i],bikes[j]))\n",
    "            return res\n",
    "        n = len(workers)\n",
    "        m = len(bikes)\n",
    "        return dfs(0,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        m, n = len(workers), len(bikes)\n",
    "        def dist(x, y):\n",
    "            return abs(x[0] - y[0]) + abs(x[1] - y[1])\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, bike):\n",
    "            if i == m:\n",
    "                return 0\n",
    "            \n",
    "            ans = inf\n",
    "            for j in range(n):\n",
    "                if (bike >> j) & 1 == 0:\n",
    "                    ans = min(ans, dfs(i + 1, bike | (1 << j)) + dist(workers[i], bikes[j]))\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from scipy.spatial.distance import cdist, cityblock\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        INF = 2 ** 31 - 1\n",
    "        d = cdist(workers, bikes, cityblock).astype(np.int64)\n",
    "        # dp\n",
    "        m = len(workers)\n",
    "        n = len(bikes)\n",
    "        dp = [INF] * (1 << n)\n",
    "        for j in range(n):\n",
    "            dp[1 << j] = d[0, j]\n",
    "\n",
    "        minval = INF\n",
    "        for i in range(1, m):\n",
    "            # 前面已分配i个\n",
    "            # 遍历前面分配的状态\n",
    "            curr = (1 << i) - 1\n",
    "            while curr < len(dp):\n",
    "                for j in range(n):\n",
    "                    if (curr >> j) & 1 == 0:\n",
    "                        nstat = curr | (1 << j)\n",
    "                        dp[nstat] = min(dp[curr] + d[i, j], dp[nstat])\n",
    "                        if i == m - 1:\n",
    "                            minval = min(minval, dp[nstat])\n",
    "                lb = curr & -curr\n",
    "                r = curr + lb\n",
    "                curr = r | ((r ^ curr) // (lb * 4))\n",
    "        return int(minval)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        m,n=len(workers),len(bikes)\n",
    "        workers.sort()\n",
    "        bikes.sort()\n",
    "        def calx(a,b,c,d):\n",
    "            return abs(a-c)+abs(b-d)\n",
    "        ans=float('inf')\n",
    "        @cache\n",
    "        def dfs(x,p,now):\n",
    "            #print(x,p,now)\n",
    "            nonlocal ans\n",
    "            if now>=ans:\n",
    "                return \n",
    "            if x==m:\n",
    "                ans=min(ans,now)\n",
    "                return\n",
    "            a,b=workers[x]\n",
    "            for i in range(n):\n",
    "                if (p>>i)&1:\n",
    "                    #p^=1<<i\n",
    "                    c,d=bikes[i]\n",
    "                    tmp=calx(a,b,c,d)\n",
    "                    dfs(x+1,p^(1<<i),now+tmp)\n",
    "        dfs(0,(1<<n)-1,0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from scipy.spatial.distance import cdist, cityblock\n",
    "from scipy.optimize import linear_sum_assignment\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        d = cdist(workers, bikes, cityblock)\n",
    "        r, c = linear_sum_assignment(d, False)\n",
    "        return int(d[r, c].sum())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def assignBikes(self, workers: List[List[int]], bikes: List[List[int]]) -> int:\n",
    "        m,n=len(workers),len(bikes)\n",
    "        workers.sort()\n",
    "        bikes.sort()\n",
    "        @cache\n",
    "        def calx(a,b,c,d):\n",
    "            return abs(a-c)+abs(b-d)\n",
    "        ans=float('inf')\n",
    "        @cache\n",
    "        def dfs(x,p,now):\n",
    "            #print(x,p,now)\n",
    "            nonlocal ans\n",
    "            if now>=ans:\n",
    "                return \n",
    "            if x==m:\n",
    "                ans=min(ans,now)\n",
    "                return\n",
    "            a,b=workers[x]\n",
    "            for i in range(n):\n",
    "                if (p>>i)&1:\n",
    "                    #p^=1<<i\n",
    "                    c,d=bikes[i]\n",
    "                    tmp=calx(a,b,c,d)\n",
    "                    dfs(x+1,p^(1<<i),now+tmp)\n",
    "        dfs(0,(1<<n)-1,0)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
